package Solution_1;

//以先序遍历的方法创建 中序遍历序列辅助分出左右节点
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
         this.val = val;
    }
}
public class Solution {
    //如果不定义成成员变量 在函数递归回退的时候perIndex的值也会回退
    //那数组就不能一个一个往下走 值会出错
    public int perIndex;
    public TreeNode buildTree(int[] preorder,int[] inorder) {
        return buildTreeChild(preorder,inorder,0, preorder.length - 1);
    }
    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inBegin,int inEnd) {
        if(inBegin > inEnd) {
            return null;
        }
        //根据前序遍历 根 左 右
        //先创建根节点 然后在中序遍历中找到该节点对应的下标
        //以下标分割为左右子树 创建左子树和右子树 用递归来实现
        TreeNode root = new TreeNode(preorder[perIndex]);
        int rootIndex = findIndex(inorder,inBegin,inEnd,preorder[perIndex]);
        perIndex++;
        //找到中间结点下标之后 下标左边是左子树 右边是右子树
        root.left = buildTreeChild(preorder,inorder,inBegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inEnd);
        return root;
    }
    public int findIndex(int[] inorder,int inBeing,int inEnd,int key) {
        for (int i = inBeing; i <= inEnd ; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}
